package com.caochenlei.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        int temp[] = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int middle = (left + right) / 2;                //首先获取中间索引
            mergeSort(arr, left, middle, temp);             //向左递归进行分解
            mergeSort(arr, middle + 1, right, temp);    //向右递归进行分解
            merge(arr, left, middle, right, temp);          //合并左右两个数组
        }
    }

    public static void merge(int[] arr, int left, int middle, int right, int[] temp) {
        int pl = left;          //定义一个指针，指向左边有序序列的初始索引
        int pr = middle + 1;    //定义一个指针，指向右边有序序列的初始索引
        int i = left;           //定义一个指针，指向temp数组的初始化索引
        //比较左右两边序列中的元素大小，把小的数填充到 temp
        while (pl <= middle && pr <= right) {
            if (arr[pl] <= arr[pr]) {
                temp[i++] = arr[pl++];
            } else {
                temp[i++] = arr[pr++];
            }
        }
        //左边的有序序列还有剩余的元素，就全部填充到 temp
        while (pl <= middle) {
            temp[i++] = arr[pl++];
        }
        //右边的有序序列还有剩余的元素，就全部填充到 temp
        while (pr <= right) {
            temp[i++] = arr[pr++];
        }
        //将 temp 数组中的元素拷贝到 arr 数组对应位置处
        for (int index = left; index <= right; index++) {
            arr[index] = temp[index];
        }
    }
}
